Hadwiger’s Conjecture

Abstract: Hadwiger’s conjecture from 1943 states that for every integer $t\ge 1$, every graph either can be t-colored or has a subgraph that can be contracted to the complete graph on t + 1 vertices. This is a far-reaching generalization of the Four-Color Theorem and perhaps the most famous conjecture in graph theory. In this talk we will survey the history of Hadwiger’s conjecture and the main ideas of recent results.

combinatorics

Audience: researchers in the topic

Comments: pw 030303

SCMS Combinatorics Seminar

Series comments: Check scmscomb.github.io/ for more information